//归并排序

    #pragma once

//归并两个有序序列a[Low..mid] [mid+1..high]
 //归并序列 [mid+1..high] 到b[Low..high]
 template <typename E>
 void Merge(E a[],E b[],int low,int mid,int high)
 {
 int i=low, j = mid+1, k=low;
 while(i<=mid&&j<=high)
    b[k++]=(a[i]<=a[j])?a[i++] : a[j++];
    while(i<=mid) b[k++]=a[i++];
    while(j<=high) b[k++]=a[j++];
 //复制b[Low..high] 到a[Low..high]
 for(int i=low;i<=high;i++) a[i] =b[i];
 }
//归并排序
template <typename E>
void MSort(E a[],E b[],int low,int high)
{
    if(Low>=high) return;

    int mid=(low+high) /2;
 MSort(a, b, Low,mid);
 MSort(a,b,mid+1, high);
    Merge(a,b, Low, mid,high);
}
//归并排序
template<typename E>
void MergeSort(Ea[],int n)
{
    auto b=new E[n];
 M Sort(a, b,0, n-1);
 delete[] b;
 }